#include<iostream>
#include<sys/time.h>
#include<vector>
#include<queue>
#include<math.h>
using namespace std;
vector<int*>v;
int doTimes = 20;
vector<queue<int>>vq;
int mul = 2000;
void initial()
{
        int temp = 0;
        int temp2 = 0;
        int num = 0;
        for(int i = 1;i <= doTimes; i++)
        {
                temp2 = i * mul;
                temp = pow(2,i);
                queue<int>q;
                int *t = new int[temp];
                for(int p = 0; p < temp; p++)
                {
                        num = rand()%10 + 1;
                        q.push(num);
                        t[p] = num;
                }
                v.push_back(t);
                vq.push_back(q);
        }
}
int optimize(int *&m ,int start, int end)
{
        if(start == end || start == end - 1)
        {
                return m[start];
        }
        return optimize(m, start, (start + end) / 2) + optimize(m, (start + end) / 2, end);
}
void optimize3(int * m, int n)
{
        int sum1 = 0, sum2 = 0;
        for(int i = 0; i < n/2; i++)
        {
                sum1 += m[i];
                sum2 += m[i + 1];
        }
        int sum = sum1 + sum2;
}
void optimize2(int * m, int n)
{
        for(int i = n; i > 1; i/=2)
        {
                for(int p = 0; p < i/2; p++)
                {
                        m[p] = m[p * 2] + m[p * 2 + 1];
                        //m[p] += m[i - p - 1];
                }
        }
}
void tradition(int * m, int len)
{
        unsigned long long sum = 0;
        for(int i = 0; i < len; i++)
        {
                sum += m[i];
        }
}
void queueOptimize(queue<int>q)
{
        int temp = 0;
        while(q.size() > 1)
        {
                temp = q.front();
                q.pop();
                q.push(q.front() + temp);
                q.pop();
        }
}
int main()
{
        struct timeval t1,t2;
        double timeuse;
        initial();
        int temp = 0;
        int temp2 = 0;
        for(int i = 1; i <= doTimes; i++)
        {
                temp2 = i * mul;
                temp = pow(2,i);
                gettimeofday(&t1,NULL);
                //optimize(v[i - 1], 0, temp);
                //tradition(v[i - 1], temp);
                //optimize2(v[i - 1], temp);
                //optimize3(v[i - 1], temp);
                queueOptimize(vq[i - 1]);
                gettimeofday(&t2,NULL);
                timeuse = (t2.tv_sec - t1.tv_sec) + (double)(t2.tv_usec - t1.tv_usec)/1000.0;
                cout<<i<<" "<<timeuse<<endl;  //输出时间（单位：ｓ）
        }
        //getchar();
        return 0;
}
